package com.example.kmp34.kmp;

/**
 * @description kmp 算法
 * @auther lijiewei
 * @date 2021/12/24 11:33
 */
public class Kmp {

    /**
     * kmp 算法，查找匹配字符串开始下标
     * @param a 主串
     * @param n 主串长度
     * @param b 模式串
     * @param m 模式串长度
     * @return
     * @author lijiewei
     * @date   2021/12/24 11:40
     */
    public static int kmp(char[] a, int n, char[] b, int m) {
        int[] next = getNexts(b, m);
        //模式串上坏字符的下标
        int j = 0;
        for (int i = 0; i < n; i++) {
            while (j>0 && a[i] != b[j]) {
                //滑动 k 位，相当于把 k 赋值给 j
                j = next[j - 1]+1;
            }
            //比较原来的坏字符
            if (a[i] == b[j]) {
                j++;
            }
            //找到匹配模式串了
            if (j == m) {
               return i-m+1;
            }
        }
        //没有匹配的
        return  -1;
    }

    /**
     * 获取所有的可匹配后缀子串
     * @param b 模式串
     * @param m 模式串长度
     * @return
     * @author lijiewei
     * @date   2022/1/13 16:53
     */
    private static int[] getNexts(char[] b, int m) {
        //abxabcabxabx
        int[] next = new int[m];
        next[0] = -1;
        int k = -1;
        for (int i = 1; i < m; i++) {
            while (k != -1 && b[k+1] != b[i]) {
                k = next[k];
            }
            if (b[k+1] == b[i]) {
               ++k;
            }
            next[i] = k;
        }
        return next;
    }
}
